(0) Obligation:
The Runtime Complexity (innermost) of the given
CpxTRS could be proven to be
BOUNDS(1, n^1).
The TRS R consists of the following rules:
not(true) → false
not(false) → true
odd(0) → false
odd(s(x)) → not(odd(x))
+(x, 0) → x
+(x, s(y)) → s(+(x, y))
+(s(x), y) → s(+(x, y))
Rewrite Strategy: INNERMOST
(1) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2.
The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1, 2, 3]
transitions:
true0() → 0
false0() → 0
00() → 0
s0(0) → 0
not0(0) → 1
odd0(0) → 2
+0(0, 0) → 3
false1() → 1
true1() → 1
false1() → 2
odd1(0) → 4
not1(4) → 2
+1(0, 0) → 5
s1(5) → 3
false1() → 4
not1(4) → 4
s1(5) → 5
true2() → 2
true2() → 4
false2() → 2
false2() → 4
0 → 3
0 → 5
(2) BOUNDS(1, n^1)